'''
bubble
'''
a = [3, 23, 78, 19, 21, 99, 5, 101, 18]

def bubble_sort(arr : list[int]):
    n = len(arr)
    if not arr or n < 1 :
        return
    for i in range(n - 1):   #总共循环n-1
        flag = False
        for j in range(n - i -1):  #每次循环预留最后一个不做比较
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                flag = True
        if flag == False : break
    return


print(bubble_sort(a))  # 打印None
print(a)

'''
selection
'''
a = [3, 23, 78, 19, 21, 99, 5, 101, 18]

def selection_sort(arr : list[int]):
    n = len(arr)
    if not arr or n < 1 :
        return
    for i in range(n - 1):
        min_index= i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
#             min_index = j if arr[j] < arr[min_index] else min_index 
        arr[i], arr[min_index] = arr[min_index], arr[i]              
    return


print(selection_sort(a))
print(a)

'''
插入
'''
a = [3, 23, 78, 19, 21, 99, 5, 101, 18]

def insert_sort(arr : list[int]):
    n = len(arr)
    if not arr or n < 2 :
        return
    for i in range(1, n):   #1,n 是待排序
        j = i - 1
        while j >= 0 and arr[i] < arr[j]:    # 可以分为最好时间复杂度，最坏复杂度，平均复杂度， 因为可以提前结束循环
            arr[j], arr[j + 1] = arr[j + 1], arr[j]
            j -= 1             
    return

def insert_sort(arr : list[int]):
    n = len(arr)
    if not arr or n < 2 :
        return
    for i in range(1, n):       #1,n 是待排序
        value= arr[i]
        j = i - 1
        while j >= 0 and value < arr[j]:    # 可以分为最好时间复杂度，最坏复杂度，平均复杂度， 因为可以提前结束循环
            arr[j+1] = a[j]
            j -= 1
        arr[j + 1] = value             
    return

print(insert_sort(a))
print(a)

'''
归并排序
'''
def divide_conquer_sort(arr : list[int]) :
    if not arr or len(arr) < 2 : return
    def d_c_sort(arr : list[int], left : int, right : int) :
        if left == right : return  # 容易出错
        mid = left + ((right - left) >> 1) #要加括号
        d_c_sort(arr, left, mid)
        d_c_sort(arr, mid + 1, right)
        def conquer(arr : list[int], left : int, mid : int, right : int):
            pl = left
            pr = mid + 1
            aux = []
            while pl <= mid and pr <= right :
                if arr[pl] <= arr[pr] :
                    aux.append(arr[pl])
                    pl += 1
                else :
                    aux.append(arr[pr])
                    pr += 1
            while pl <= mid:
                aux.append(arr[pl])
                pl += 1
            while pr <= right:  #要控制索引的范围
                aux.append(arr[pr])
                pr += 1
            i = 0
            for i in range(right - left + 1):
                arr[left + i] = aux[i]
                i += 1
        conquer(arr, left, mid, right)
    d_c_sort(arr, 0, len(arr) - 1)

''' 
 qsort 快排

'''
def patition(nums: list, left: int, right: int) -> list:
    less = left - 1
    more = right
    while left < more:
        if nums[left] < nums[right] :
            less += 1
            nums[less], nums[left] = nums[left], nums[less]
            left += 1
        elif nums[left] == nums[right]:
            left += 1
        else :
            more -= 1
            nums[left], nums[more] = nums[more], nums[left]
    nums[more], nums[right] = nums[right], nums[more]
    return [less + 1, more]


def q_sort_internel(nums: list, left: int, right: int):
    if left < right:
        tmp = left + random.randint(0, right - left)  #random.randint 这个函数输出结果时包括右边界的
        nums[tmp], nums[right] = nums[right], nums[tmp]
        q = patition(nums, left, right)
        q_sort_internel(nums, left, q[0] - 1)
        q_sort_internel(nums, q[1] + 1, right)


def q_sort(nums: list):
    if not nums or len(nums) < 2: return
    q_sort_internel(nums, 0, len(nums) -1)
"""
堆排序
"""
#当堆顶元素，变化时调整堆
def heapify(nums: list, i: int, heapsize: int):
    left = 2 * i + 1
    while left < heapsize: #左孩子不出界
        if left + 1 < heapsize and nums[left] < nums[left + 1]:
            largest = left + 1
        else: largest = left
        if nums[largest] < nums[i]:
            largest = i
        if largest == i: break
        nums[i], nums[largest] = nums[largest], nums[i]
        i = largest
        left = 2 * i + 1

# 构建堆，(i - 1) // 2 父节点
def heap_insert(nums: list, i: int):
    while i > 0 and nums[i] > nums[(i - 1) // 2] :
        nums[i], nums[(i - 1) // 2] = nums[(i - 1) // 2],nums[i]
        i = (i - 1) // 2


def heap_sort(nums: list):
    size = len(nums)
    if not nums or size < 2: return
# nlogn的时间复杂度，如果客户是动态的给数组中的元素，所以只能用这种复杂度的方法来建堆
#    for i in range(size):
#        heap_insert(nums, i)

#下面的建堆过程时间复杂度O(N), 但是使用场景仅限于一开始就确定的静态数组，动态数组不行
    i = len(nums) - 1
    while i >= 0:
        heapify(nums, i, len(nums))
        i -= 1 

    # 排序，把最后一个元素移出，相当于已经排好了
    size -= 1
    nums[0], nums[size] = nums[size], nums[0]
    while size > 0:
        heapify(nums, 0, size)
        #把倒数第几个元素移出，相当于已经排好了
        size -= 1
        nums[0], nums[size] = nums[size], nums[0]


import heapq
'''
newl = [-ll for i in ll]  把原数组取反，那么最小堆就变成最大堆
几乎有序数组的排序：
几乎有序： 如果把数组排好序的话，每个元素移动的距离不超过k,
并且相比数组长度来说，k很小
#O(NlogK)  k很小
'''

def sorted_arrdistance_less_k(arr: list, k: int):
    ini_len = min(len(arr) - 1 , k)
    index = 0
# 先把0~k 这k+1个元素放入最小堆
    heap = []
    for index in range(ini_len + 1):
        heapq.heappush(heap, arr[index])
    i = 0
#从k+1元素开始，进入一个，再出来一个
    while index < len(arr):
        arr[i] = heapq.heappop(heap)
        heapq.heappush(heap, arr[index])
        i += 1
        index += 1
# 把队中剩余元素放入数组
    while len(heap) >= 0:
        arr[i] = heapq.heappop(heap)
        i += 1


"""
桶排序（计数排序）, 只适合桶里面的数组是正整数的场景，如果是小数，或者负数则需要变化为正整数
"""
def count_sort(nums: list):
    if not nums or len(nums) < 2: return

    #import sys
    #imax = -sys.maxsize - 1  # 系统中的普通64位 整数最小值，而不是长整数
    imax = nums[0]
    for i in nums:
        imax = max(i, imax)  # 求取数组最大值
    bucket = [0] * (imax + 1)

    for i in nums:
        bucket[i] += 1
    j = 0
    for i in range(len(bucket)):    # bucket数组中有空洞，中间很多浪费的。所以数组大小最好限制在200以内
        while bucket[i] > 0:
            nums[j] = i
            j += 1
            bucket[i] -= 1


""" 剑指 Offer 51. 数组中的逆序对, 对分治思想的练习,降序排列
"""
class Solution:
    def d_c_sort(self, nums: List[int], left : int, right : int) -> int:
        if left == right : return 0
        mid = left + ((right - left) >> 1)
        def conquer(nums: list[int], left: int, mid: int, right: int) -> int:
            aux = []
            pl = left
            pr = mid + 1
            res = 0
            while pl <= mid and pr <= right:
                if nums[pl] <= nums[pr]:
                    aux.append(nums[pr])
                    pr += 1
                else:
                    res += right - pr + 1
                    aux.append(nums[pl])
                    pl += 1
            while pl <= mid :
                aux.append(nums[pl])
                pl += 1
            while pr <= right:
                aux.append(nums[pr])
                pr += 1
            for i in range(right - left + 1):
                 nums[left + i] = aux[i]
            nums[left:right+1] = aux[:]
            return res
        return self.d_c_sort(nums, left, mid) + self.d_c_sort(nums, mid + 1, right)\
            + conquer(nums, left, mid, right)

    def reversePairs(self, nums: List[int]) -> int:
        if not nums or len(nums) < 2 :
            return 0
        return self.d_c_sort(nums, 0, len(nums) - 1)
        
''' 剑指 Offer 51. 数组中的逆序对, 对分治思想的练习,升序排列
'''
class Solution:
    def d_c_sort(self, nums: List[int], left : int, right : int) -> int:
        if left == right : return 0
        mid = left + ((right - left) >> 1)
        def conquer(nums: list[int], left: int, mid: int, right: int) -> int:
            aux = []
            pl = left
            pr = mid + 1
            res = 0
            for i in range(left, right + 1):
                if pl > mid:
                    aux.append(nums[pr])
                    pr += 1
                elif pr > right:
                    aux.append(nums[pl])
                    pl += 1
                    res +=  right - mid  # 右边元素的个数就是逆序对
                elif nums[pl] <= nums[pr]:
                    aux.append(nums[pl])
                    pl += 1
                    res += pr - mid - 1
                else: # nums[pl] > nums[pr]:
                    aux.append(nums[pr])
                    pr += 1 
            nums[left:right+1] = aux[:]
            return res
        return self.d_c_sort(nums, left, mid) + self.d_c_sort(nums, mid + 1, right)\
            + conquer(nums, left, mid, right)

    def reversePairs(self, nums: List[int]) -> int:
        if not nums or len(nums) < 2 :
            return 0
        return self.d_c_sort(nums, 0, len(nums) - 1)

'''
###
###  315. 计算右侧小于当前元素的个数
'''
class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        """ 在「前有序数组」的元素归并的时候，数一数「后有序数组」已经归并回去的元素的个数，因为这些已经出列的元素都比当
        前出列的元素要（严格）小. 但是在「归并」的过程中，元素的位置会发生变化，因此下一步需要思考如何定位元素；
        根据「索引堆」的学习经验，一个元素在算法的执行过程中位置发生变化，
		我们还想定位它，可以使用「索引数组」，技巧在于：「原始数组」不变，用于比较两个元素的大小，真正位置变化的是
        「索引数组」的位置；「索引数组」技巧建立了一个一一对应的关系，记录了当前操作的数对应的「原始数组」的下标。 
        「归并排序」还需要一个用于归并的辅助数组，
		这个时候拷贝的就是索引数组的值了。
		"""
		
        size = len(nums)
        if size == 0:
            return []
        if size == 1:
            return [0]
        temp = [-1 for _ in range(size)]  #临时的存放索引的数组，都初始化为-1
        res = [0 for _ in range(size)]    #最后要返回的数组
        # 索引数组，作用：归并回去的时候，方便知道是哪个下标的元素
        indexes = [i for i in range(size)]

        self.d_c_and_count_smaller(nums, 0, size - 1, temp, indexes, res)  #divide_conquer
        return res

    def d_c_and_count_smaller(self, nums, left, right, temp, indexes, res):
        if left == right:
            return
        mid = left + ((right - left) >> 1)  # left + (right - left) // 2  （//整除）
        self.d_c_and_count_smaller(nums, left, mid, temp, indexes, res)
        self.d_c_and_count_smaller(nums, mid + 1, right, temp, indexes, res)

        # 代码走到这里的时候，[left, mid] 和 [mid + 1, right] 已经完成了排序并且计算好右侧小于每个元素的个数
        if nums[indexes[mid]] <= nums[indexes[mid + 1]]:
            # 此时不用计算横跨两个区间的右侧小于每个元素的个数，直接返回
            # 为什么不用？当前if条件满足时，说明[mid + 1, right]所有数字都比[left, mid]的大，继续计算右侧小于每个元素的个数没有意义，
			#相当于剪枝。
            #所以说是按照升序？
            return
        self.merge_and_count_smaller(nums, left, mid, right, temp, indexes, res)
    
    def merge_and_count_smaller(self, nums, left, mid, right, temp, indexes, res):
        # [left,mid] 前有序数组, [mid+1,right] 后有序数组
        # 先拷贝，再合并
        # 由于前数组和后数组都有序，此时若出现后数组元素较大或者指针出界的情况，说明之前存在后数组元素较小的情况。需要计算后数组小于
		#当前元素的个数并累计到res中。
        for i in range(left, right + 1):
            temp[i] = indexes[i]
        pl = left
        pr = mid + 1
        for cur in range(left, right + 1):
            # 每一次合并nums，都需要判断数组下标是否越界。
            if pl > mid:
                # pl > mid 表示 pl已经遍历完了第一个部分的所有数，mid 是第一个部分的最后一个位置的下标。所以当前合并过程可以忽略pl坐标，
				#直接把j坐标所在元素合并到 indexes。
                indexes[cur] = temp[pr]
                pr += 1
            elif pr > right:
                # 表示 pr 已经遍历完了第二个部分的所有数， right 是第二个部分的最后一个位置的下标。所以当前合并过程可以忽略pr坐标，
				#直接把pl坐标所在元素合并到 indexes。
                indexes[cur] = temp[pl]
                pl += 1
                # 后数组中的所有数字都比cur对应的元素小；把结果放入res
                res[indexes[cur]] += (right - mid)
            # 走到这里时，说明i，j都没有越界，可以直接比较、合并到 indexes。
            elif nums[temp[pl]] <= nums[temp[pr]]:  # temp[xx] 表示原始数组的顺序
                # 此时前数组元素出列，需要统计右侧小于当前元素的个数
                indexes[cur] = temp[pl]
                pl += 1 #因为时升序排列，所以就合并左边数组
                # 后数组中的[mid, pr - 1]对应都比cur对应的元素小（很显然不包含当前pr元素）；把结果放入res
                res[indexes[cur]] += (pr - mid - 1)
            else:  #相当于 nums[temp[pl]] > nums[temp[pr]]:
                # 此时后数组元素出列，不统计右侧小于当前元素的个数
                indexes[cur] = temp[pr]
                pr += 1
"""
我们可以把最后的问题进行分解，采用归并排序（升序排列）的思想。其中为了找到每一个数据对于的下标位置，所有我们数组的元素类型为一个
pair类型的结构体，第一个元素是数据，第二个元素是数据对应的下标

而对于归并排序而言，我们需要做手脚的地方有以下四点：（已知，le，mid，ri）

当左边区间遍历完毕，i = mid + 1。那么右边区间就直接插入对应位置，不需要处理，因为右边区间剩余的元素都是比左边区间大的。
当右边区间遍历完毕，i = ri + 1。那么左边区间就需要插入对于位置，这个时候需要进行处理，因为左边区间的此时的元素都是比右边区间所有元素大的，
    所以需要加上右边区间的元素个数ri - mid
比较小的元素在左边区间的位置。在插入的同时，记录右边区间已经使用的元素个数，pr - mid - 1

比较小的元素在右边区间的位置。也是不需要进行处理的，因为他右边比他小的数在上一步的归并中已经处理了。
    (直接过，直到右边比左边大时，统一计数)
"""